Lists are common data structures to keep related data/items together. Lists are also fundamental building blocks used to implement other data structures, such as stacks, queues, and the like. While there are numerous operations that may be implemented with regard to a list, updating the arrangement or configuration of a list can be distilled down to two basic actions: adding an item to the list and deleting an item from the list.
When a process has exclusive access to a list, adding or deleting a list item is relatively straightforward. However, multi-process access to a list is unwieldy because a list can only reasonably be added to by a single process at any given time. More particularly, when a first process gains write access in order to update a list, all other access to the list by other processes is excluded, i.e., a second process is not allowed to read or write to the list. Of course, while read access will not modify the list, it must still be restricted during a write operation as the read operation may encounter inconsistent/wrong results while the write operation is in progress.
In fact, many computer operating systems, server software, and user applications make extensive use of linked lists in such varied settings as memory management/allocation, file systems, library management, and the like. Thus, as is appreciated by those skilled in the art, in many (if not all) of these settings, the lists may be accessed by more than one concurrently executing process. Unfortunately, until now, even in a multi-process/multi-tasking system, when one process is writing to a list, all other access to that list by other processes is blocked. Moreover, this blockage can seriously impact the overall performance of the computer system.